package name.huzhenbo.java.algorithm.sort;

class QuickSorter implements Sorter {
    /**
     * Complexity: worst: O(n2),  best: O(nlogn)
     *
     * @param input
     * @return
     */
    public int[] go(int[] input) {
        _quickSort(input, 0, input.length - 1);
        return input;
    }

    private void _quickSort(int[] input, int start, int end) {
        if (start >= end) {
            return;
        }
        int base = start;
        for (int i = start + 1; i <= end; i++) {
            if (input[i] < input[start]) {
                if (i == base + 1) base++;
                else SorterUtil.swap(input, ++base, i);
            }
        }
        SorterUtil.swap(input, start, base);
        _quickSort(input, start, base - 1);
        _quickSort(input, base + 1, end);
    }
}
